With the recent development of network communications and electronic transactions, maintenance of security in communications has become a critical issue. One method of maintaining security is cryptography. Currently, communications using various cryptographic techniques are actually performed.
For example, systems have been put into practical use in which an encryption processing module is embedded in a compact device such as an IC card and data transmission and reception is performed between the IC card and a reader/writer serving as a data read/write device so that authentication processing or encryption and decryption of transmission/reception data is performed.
There are various cryptographic algorithms. According to a rough classification, the cryptographic algorithms are classified into public-key cryptography in which an encryption key and a decryption key are set as different keys, such as, for example, a public key and a secret key, and common-key cryptography in which an encryption key and a decryption key are set as a common key.
There are various algorithms in common-key cryptography. One of such algorithms is a cryptography in which a plurality of keys are generated on the basis of a common key and data transformation processing is repeatedly performed in units of blocks (64 bits, 128 bits, etc.) by using the generated plurality of keys. A typical algorithm using the key generation method and the data transformation processing is common-key blockcipher cryptography.
As typical common-key blockcipher algorithms, for example, the DES (Data Encryption Standard) algorithm, which was the U.S. standard cryptography, the AES (Advanced Encryption Standard) algorithm, which is the current U.S. standard cryptography, and the like are known.
Such a common-key blockcipher algorithm is mainly constituted by an encryption processing part including round-function executing parts that repeatedly perform transformation of input data, and a key scheduling part generating a round key used for each of the rounds of the round-function parts. The key scheduling part first generates an expanded key with an increased number of bits on the basis of a master key (primary key), which is a secret key, and generates a round key (sub-key) used for each of the round-function parts of the encryption processing part on the basis of the generated expanded key.
As a specific structure for implementing such an algorithm, a structure in which a round function including a linear transformation part and a non-linear transformation part is iterated is known. For example, a typical structure is a Feistel structure. The Feistel structure is a structure in which plaintext is transformed into ciphertext by simple iterations of round functions (F-functions) serving as data transformation functions. In the round functions (F-functions), linear transformation processing and non-linear transformation processing are performed. Note that as documents describing cipher processing using the Feistel structure, for example, non-patent document 1 and non-patent document 2 are available.
In the common-key blockcipher processing or, for example, hash function, data transformation based on non-linear transformation processing is performed. Non-linear transformation functions called S-boxes can be used in non-linear transformation. The S-boxes are elements of a blockcipher or a hash function, and are very important functions for determining its security or performance of implementation. The S-boxes are generally non-linear transformation functions with n-bit input and m-bit output. S-boxes with the same number of input and output bits and an input-output relation of one-to-one correspondence are referred to as bijective S-boxes.
In a case where S-boxes are used for the non-linear transformation of the encryption processing, properties of the applied S-boxes greatly affect the encryption security. That is, various cryptanalytic attacks such as, for example, differential attacks and linear attacks, are known. The higher the difficulty of key or algorithm analysis by such cryptanalytic attacks, the higher the security. The security largely depends on the properties of S-boxes used in a blockcipher or a hash function.
For example, it is generally difficult to strictly evaluate the security of the overall cryptographic algorithm or round functions applied to cipher processing because the input and output size is large (for example, 64 bits, 128 bits, etc.). However, the input and output size of S-boxes is generally small, for example, about 8-bit input and output, and a strict security evaluation can be achieved. The fact that in order to improve the security of the overall cryptographic algorithm, at least the characteristics listed below are required for S-boxes is known.
(1) The maximum differential probability is sufficiently small.
(2) The maximum linear probability is sufficiently small.
(3) The order of a Boolean algebra represented by a Boolean polynomial is sufficiently high.
(4) The number of terms in the polynomial representation of the input and output is sufficiently large.
Mainly, the characteristic (1) determines the resistance to the differential attacks, the characteristic (2) determines the resistance to the linear attacks, the characteristic (3) determines the resistance to higher order differential attacks, and the characteristic (4) determines the resistance to interpolation attacks. Furthermore, in order to improve the security, it is important to have a low correlation between input and output bits of S-boxes, to have a change rate in the output of about ½ with respect to one-bit change in the input, etc.
Also, in addition to the requirement for high security, high performance of implementations is also required for S-boxes. For example, in an implementation structure in which software-based cipher processing or hash function is performed, a structure in which generally, a table indicating an output with respect to an input is stored in a memory and non-linear transformation processing is performed using a technique called table lookup (table implementation) is implemented. Thus, the implementation performance does not greatly depend on the internal structure of the S-boxes. However, in hardware-based implementations, a circuit to calculate a specific output on the basis of, for example, an input value is configured. This circuit configuration largely depends on the applied S-boxes, and the size of the circuit is also affected by the S-boxes.    Non-Patent Document 1: K. Nyberg, “Generalized Feistel networks”, ASIACRYPT '96, Springer Verlag, 1996, pp. 91-104.    Non-patent Document 2: Yuliang Zheng, Tsutomu Matsumoto, Hideki Imai On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. CRYPTO 1989: 461-480.